In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch, such as an if-then-else structure in a program or code, will go before this is known for sure. A branch predictor implements a method of branch prediction. Branch prediction improves the flow in an instruction pipeline and plays a role in achieving high effective performance in many microprocessor architectures.
Branch prediction is based on branch history, that is, a record of how often a given branch is taken and not taken. In a global branch history, the branch histories of multiple branches are stored in one set of bits.
FIG. 2 shows a traditional type of processing device and method used to update a global branch history. Circuitry determines whether or not a branch has been found (step 225). When a branch has not been found, a current global history is unchanged (step 220). When a branch is found, the current global branch history is shifted by one bit (step 215; shown as a left shift) and the oldest history bit (bit 3) is lost. The rightmost bit in the current global branch history is replaced by a bit indicating whether or not the branch has been taken (step 230)—for example, a 0 for not taken and a 1 for taken. In this manner, the current global branch history is updated. The current branch history is used in a branch predictor to predict whether a branch will be taken or not taken in the future.